1. Field of Invention
The present invention relates generally to navigation systems and location-based information delivery, and more particularly, to a method and system for prediction-based positioning and delivering real-time navigational information using distributed navigation information processing.
2. Description of Related Art
Presently, a rapid growth in technological fields such as the personal digital assistant (PDA) and cellular telephones has fueled consumer interest in products that provide on-call real-time guidance and communication. One such technological advance is a navigation system that allows its users to reach destinations by providing turn-by-turn instructions along a calculated route.
Conventional navigation systems are typically satellite-based global positioning system (GPS) devices which have been incorporated into automobile navigation systems, for additional information regarding conventional navigation systems, refer to U.S. Pat. Nos. 5,938,720, 5,928,307, 5,922,042, 5,912,635, 5,910,177, 5,904,728, 5,902,350, all incorporated herein by reference. Such conventional automobile navigation systems, however, are expensive and inconvenient to use. Therefore, there is a need to incorporate navigation capabilities so that a user may access real-time turn-by-turn route instructions via personal handheld devices such as a wireless cellular phone or a personal digital assistant (PDA) device.
Several technical obstacles prevent efficient use of navigation systems incorporated into personal handheld devices. One such obstacle is the amount of geographic data needed to provide reasonably detailed navigational information. Small handheld devices comprise limited embedded memory that may not be adequate for storing a large amount of geographic information essential for navigational purposes. This obstacle can be overcome in a distributed navigation system comprising a server-client structure, wherein the navigation functions are partitioned and assigned among one or more distributed servers and the handheld device or client.
However, unlike conventional real time navigation systems where routes or reroutes in cases of deviation can be calculated without the consideration of communication latency and other time delay effects, a distributed navigation system is plagued with uncertain latencies and other parameters that affect route calculation. For example, the latency incurred for both communication from the client to the server and from the server to the client must be taken into consideration for route calculation, as the server must predict a route origin location before calculating a route from the origin to the destination.
One additional parameter is the insufficient location accuracy provided by current technology. Initial sources of inaccuracy of the GPS based systems, for example, are affected by factors such as atmospheric and timing errors limiting the accuracy of a single GPS receiver to +/xe2x88x9250 meters. Inaccurate GPS information as well as other parameters such as road condition, traffic condition, and weather need to be considered in order to obtain a close approximation of the route origin location, and the origin may then be used to calculate an optimal route to the destination.
The present invention provides a method and system for prediction-based navigation in a distributed navigation system. In one embodiment of the present invention, the system comprises a personal digital device (e.g. PDA, cellular telephone, etc.) or client and one or more servers communicating with the client via wireless carriers and the Internet.
A server obtains a user""s initial position via the client and proceeds to estimate and aggregate a number of time delays such as incurred by communication between the server and the client. The server then determines a route origin location within an established comfort zone defined by a minimum and a maximum displacement from the user""s initial position by estimating the user""s speed and elapsed time since the initial position. The server establishes the comfort zone by taking into consideration a number of parameters such as speed limit or traffic condition, and estimates the route origin location within the comfort zone. The server subsequently calculates a route to the destination according to the estimated route origin location and the navigation system sends turn-by-turn instruction of the route to the user from the estimated route origin location to the destination.